/*
 * @Author: ※mk9007@163.com
 * @Date: 2021-09-25 15:04:00
 * @LastEditTime: 2021-09-25 15:07:49
 * 2021-09-25 15:04:00
 * @Route: 
 * @FilePath: \code_snippet\leetcode\minDistance\minDistance.js
 * @Description: 
 * Copyright 2021
 * U2FsdGVkX1+ZIXU/AIJgzXNmur/kcio4wZG9DMOSf+wY3GM1S6sbp4TSbCUUC2xXHYERfgUJvuVIjCHTYsH+z9FLdxCn34dmQFGj6e6rBUiCfLqp7JRkVD+XT3AcLmHj6O3WD2ZlsHMBd3Hacgtu/nxKflgOyZtb7y2X3vgYirLr+gCTiQ8GJRw9CMXhpkRq5MsOqTenZGlGeZk7f/3vA9JUwmC/qJKdeh0UmuOUr0uy4V6NKVBjYf69n+gIY6SQ
 * ◆●○★☆
 * 
 */
/**
 * leetcode:583
 * @see https://leetcode-cn.com/problems/delete-operation-for-two-strings/
 * @tag 最大公共子序列、动态规则
 * 给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
 * @param {*} word1 
 * @param {*} word2 
 * @returns 
 */
var minDistance = function(word1, word2) {
    const m = word1.length,
        n = word2.length;
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        const c1 = word1[i - 1];
        for (let j = 1; j <= n; j++) {
            const c2 = word2[j - 1];
            if (c1 === c2) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    const lcs = dp[m][n];
    return m - lcs + n - lcs;
}

minDistance('sea', 'eat');